#include "../../include/align.h"
#include "../../include/myPrintk.h"

// EMB每一个block的数据结构，userdata可以暂时不用管。
typedef struct EMB {
	unsigned long size;
	union {
		/*unsigned long*/ struct EMB*
			nextStart;           // if free: pointer to next block
		unsigned long userData;  // if allocated, belongs to user
	};
} EMB;  //共占8个字节

#define EMB_size ((unsigned long)0x8)

// dPartition 是整个动态分区内存的数据结构
typedef struct dPartition {
	unsigned long size;
	/*unsigned long*/ EMB* firstFreeStart;
} dPartition;  //共占8个字节

#define dPartition_size ((unsigned long)0x8)

void showdPartition(struct dPartition* dp) {
	myPrintk(0x5, "dPartition(start=0x%p, size=0x%x, firstFreeStart=0x%x)\n",
			 dp, dp->size, dp->firstFreeStart);
}

void showEMB(struct EMB* emb) {
	myPrintk(0x3, "EMB(start=0x%p, size=0x%x, nextStart=0x%p)\n", emb,
			 emb->size, emb->nextStart);
}

unsigned long dPartitionInit(unsigned long start, unsigned long totalSize) {
	//本函数需要实现！！！
	/*功能：初始化内存。
	1.在地址start处，首先是要有dPartition结构体表示整个数据结构(也即句柄)。
	2.然后，一整块的EMB被分配（以后使用内存会逐渐拆分），在内存中紧紧跟在dP后面，然后dP的firstFreeStart指向EMB。
	3.返回start首地址(也即句柄)。
	注意有两个地方的大小问题：
			第一个是由于内存肯定要有一个EMB和一个dPartition，totalSize肯定要比这两个加起来大。
			第二个注意EMB的size属性不是totalsize，因为dPartition和EMB自身都需要要占空间。

	*/
	totalSize = totalSize & 0xFFFFFFF8;  // align to 8

	if (totalSize < (dPartition_size_align + EMB_size_align)) return 0;

	dPartition* dp = (dPartition*)start;
	EMB* emb = (EMB*)(start + dPartition_size_align);
	dp->firstFreeStart = emb;
	dp->size = totalSize - dPartition_size_align;

	emb->size = totalSize - dPartition_size_align - EMB_size_align;
	emb->nextStart = 0;

	return start;
}

void dPartitionWalkByAddr(unsigned long dp) {
	//本函数需要实现！！！
	/*功能：本函数遍历输出EMB 方便调试
	1.先打印dP的信息，可调用上面的showdPartition。
	2.然后按地址的大小遍历EMB，对于每一个EMB，可以调用上面的showEMB输出其信息

	*/
	if (dp == 0) return;
	dPartition* pdP = (dPartition*)dp;
	showdPartition(pdP);
	EMB* pEMB = pdP->firstFreeStart;
	while (pEMB != 0) {
		showEMB(pEMB);
		pEMB = pEMB->nextStart;
	}
	return;
}

//=================firstfit, order: address, low-->high=====================
/**
 * return value: addr (without overhead, can directly used by user)
 **/

unsigned long dPartitionAllocFirstFit(unsigned long dp, unsigned long size) {
	//本函数需要实现！！！
	/*功能：分配一个空间
	1.使用firstfit的算法分配空间，当然也可以使用其他fit，不限制。
	2.成功分配返回首地址，不成功返回0
	3.从空闲内存块组成的链表中拿出一块供我们来分配空间(如果提供给分配空间的内存块空间大于size，我们还将把剩余部分放回链表中)，并维护相应的空闲链表以及句柄
	注意的地方：
			1.EMB类型的数据的存在本身就占用了一定的空间。

	*/
	if (size % ALIGN_SIZE != 0)
		size = ((size / ALIGN_SIZE) + 1) * ALIGN_SIZE;  // align

	dPartition* pdp = (dPartition*)dp;
	if (pdp->firstFreeStart == 0 || size == 0 || size >= pdp->size)
		return 0;  // illegal alloc
	EMB* pEMB = pdp->firstFreeStart;

	if (pEMB->size >= size) {                       // alloc firstfree
		if (pEMB->size <= size + EMB_size_align) {  // directly alloc it
			pdp->firstFreeStart = pEMB->nextStart;
			unsigned long addr = (unsigned long)pEMB + EMB_size_align;
			return addr;
		} else {  // divide into two parts
			EMB* newEMB = (EMB*)((unsigned long)pEMB + EMB_size_align + size);
			newEMB->nextStart = pEMB->nextStart;
			newEMB->size = pEMB->size - size - EMB_size_align;
			pEMB->size = size;
			pdp->firstFreeStart = newEMB;
			unsigned long addr = (unsigned long)pEMB + EMB_size_align;
			return addr;
		}
	}

	// firstfree is not avilable
	while (pEMB->nextStart != 0) {
		// test nextstart
		if (pEMB->nextStart->size >= size) {
			if (pEMB->nextStart->size <=
				size + EMB_size_align) {  // directly alloc it
				unsigned long addr =
					(unsigned long)(pEMB->nextStart) + EMB_size_align;
				pEMB->nextStart = pEMB->nextStart->nextStart;
				return addr;
			} else {  // divide into two parts
				EMB* newEMB = (EMB*)((unsigned long)(pEMB->nextStart) +
									 EMB_size_align + size);
				newEMB->nextStart = pEMB->nextStart->nextStart;
				newEMB->size = pEMB->nextStart->size - size - EMB_size_align;
				pEMB->nextStart->size = size;
				unsigned long addr =
					(unsigned long)(pEMB->nextStart) + EMB_size_align;
				pEMB->nextStart = newEMB;
				return addr;
			}
		}
		else pEMB=pEMB->nextStart;
	}

	return 0;  // if not avilable
}

/*
 *r
 */
unsigned long dPartitionFreeFirstFit(unsigned long dp, unsigned long start) {
	//本函数需要实现！！！
	/*功能：释放一个空间
	1.按照对应的fit的算法释放空间
	2.注意检查要释放的start~end这个范围是否在dp有效分配范围内
			返回1 没问题
			返回0 error
	3.需要考虑两个空闲且相邻的内存块的合并
	*/
	// we cannot deal with the start inside the alloc addr(e.g.:alloc 8,and
	// start=alloced+4)
	if (start & 0x00000007 != 0 || start == 0) return 0;  // if not algin of 8

	dPartition* pdp = (dPartition*)dp;

	EMB* pEMB = (EMB*)(start - 8);
	if ((unsigned long)pEMB < dp + dPartition_size_align)
		return 0;  // error of start

	unsigned long endaddr = start + pEMB->size;
	if (endaddr > dp + dPartition_size_align + pdp->size)
		return 0;  // illegal end

	EMB* EMBpre = 0;

	if (pdp->firstFreeStart != 0) {  // add to linklist
		if ((unsigned long)(pdp->firstFreeStart) >=
			endaddr) {  // firstfree is behind pEMB
			pEMB->nextStart = pdp->firstFreeStart;
			pdp->firstFreeStart = pEMB;
		} else {  // not
			EMBpre = pdp->firstFreeStart;
			while (EMBpre != 0) {
				unsigned long EMBpre_tail =
					(unsigned long)EMBpre + EMBpre->size + EMB_size_align;
				//myPrintk(0x05,"finding EMBpre_tail:%lx,pEMB:%p\n",EMBpre_tail,pEMB);
				int checkhead =
					(EMBpre_tail <=
					 (unsigned long)
						 pEMB);  // pEMB is no less than tail of EMBpre
				if (checkhead == 0)
					break;  // when head is no avilable,all below no avilable

				unsigned long EMBpre_next_head =
					(unsigned long)(EMBpre->nextStart);
				int checkend =
					(EMBpre_next_head >= endaddr) || (EMBpre_next_head == 0);
				//myPrintk(0x05,"finding EMBpre_next_head:%lx,endaddr:%p\n",EMBpre_next_head,endaddr);
				if (checkend == 0) {
					EMBpre = EMBpre->nextStart;
					continue;
				}  // when end is not avilable,continue

				// connect linklist
				pEMB->nextStart = EMBpre->nextStart;
				EMBpre->nextStart = pEMB;
				break;
			}
			if (EMBpre == 0 || EMBpre->nextStart != pEMB) return 0;  // not find
		}
	} else {
		pdp->firstFreeStart = pEMB;
		pEMB->nextStart = 0;
	}

	//myPrintk(0x05,"EMBpre:%p\n",EMBpre);//test

	// now we insert succeed, we conbine linklist
	if (EMBpre != 0) {  // if insert is not first
		unsigned long EMBpre_tail =
			(unsigned long)EMBpre + EMBpre->size + EMB_size_align;
		if (EMBpre_tail == (unsigned long)pEMB) {  // connect head
			EMBpre->size = EMBpre->size + EMB_size_align + pEMB->size;
			EMBpre->nextStart = pEMB->nextStart;
			pEMB = EMBpre;  // to make conbine tail convenient
		}
	}
	if (pEMB->nextStart != 0) {  // if insert is not end
		if (endaddr == (unsigned long)(pEMB->nextStart)) {  // connect end
			pEMB->size += (pEMB->nextStart->size + EMB_size_align);
			pEMB->nextStart = pEMB->nextStart->nextStart;
		}
	}
	return 1;
}

// wrap: we select firstFit, you can select another one
// user need not know this
unsigned long dPartitionAlloc(unsigned long dp, unsigned long size) {
	return dPartitionAllocFirstFit(dp, size);
}

unsigned long dPartitionFree(unsigned long dp, unsigned long start) {
	return dPartitionFreeFirstFit(dp, start);
}
